
/**

 * Copyright (c) 2010,  Joel Andersson, Olle Br�nnlund, Hannes Gustafsson All rights reserved.

 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:

 *          - Redistributions of source code must retain the above copyright
 *          notice, this list of conditions and the following disclaimer.  
 *          - Redistributions in binary form must reproduce the above copyright
 *          notice, this list of conditions and the following disclaimer in the
 *          documentation and/or other materials provided with the
 *          distribution. 
 *          - Neither the name of the owner nor the names of its contributors
 *          may be used to endorse or promote products derived from this
 *          software without specific prior written permission.

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
import java.awt.Point;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Random;

/**
 *
 * @author Joel Andersson, Olle Br�nnlund, Hannes Gustafsson
 */
public class EmptyRectangleContainer {

    private int x;
    private int y;
    private int seed;
    private ArrayList<Point> pts = new ArrayList<Point>(); /* this will be a sorted list of points */

    private ArrayList<Rectangle> allMaximalRectangles = new ArrayList<Rectangle>();
    private ArrayList<Rectangle> emptyRectangles = new ArrayList<Rectangle>();
    protected ArrayList<Rectangle> rectangleList;

    /* this will contain the solution but is not used atm */
    private ArrayList<Rectangle> solutionList = new ArrayList<Rectangle>();

    /* this is used instead. the array contains the index of the rectangles in the solution */
    protected int[] solutionArray;
    protected int max = 0;
    protected int calls = 0; /* call counter for branch and bound */

    protected int indexSmallestRec = 0; /* how "deep" are we searching for a solution */


    /**
     *
     * @param x
     * @param y
     */
    public EmptyRectangleContainer(int x, int y, int numPts, int seed, boolean onlyMER, int minimumArea) {

        this.x = x;
        this.y = y;
        this.seed = seed;
        generatePts(numPts, seed);


        if (onlyMER) {
            long start = System.currentTimeMillis();
            this.generateAllMaximalRectangles();
            long end = System.currentTimeMillis();
            this.rectangleList = this.allMaximalRectangles;
            System.out.format("Used seed: %49s\n" +
                    "Number of maximal empty rectangles found: %18s\n" +
                    "Execution time finding all empty rectangles: %15s ms\n", this.seed, this.rectangleList.size(), (end - start));
        } else {
            long start = System.currentTimeMillis();
            this.generateEmptyRectangles(minimumArea);
            long end = System.currentTimeMillis();
            this.rectangleList = this.emptyRectangles;
            System.out.format("Used seed: %49s\n" +
                    "Number of empty rectangles found: %26s\n" +
                    "Execution time finding all empty rectangles: %15s ms\n", this.seed, this.rectangleList.size(), (end - start));
        }
    }

    /**
     *
     * @param numPts
     * @param seed
     */
    private void generatePts(int numPts, int seed) {

        Random rnd;

        /* if there's a request for a specific seed we generate it,
         * otherwise produce a random seed */
        if (seed == 0) {
            rnd = new Random();
            this.seed = rnd.nextInt();
            rnd.setSeed(this.seed);
        } else {
            this.seed = seed;
            rnd = new Random(seed);
        }

        /* produce the points and add them to our list */
        for (int i = 0; i < numPts; i++) {
            this.pts.add(new Point(rnd.nextInt(this.x), rnd.nextInt(this.y)));
        }

        /* sort the list by x and then y in ascending order */
        Collections.sort(this.pts, (new Comparator<Point>() {

            public int compare(Point a, Point b) {
                if (a.x > b.x) {
                    return 1;
                } else if (b.x == a.x) {
                    if (a.y > b.y) {
                        return 1;
                    } else if (a.y == b.y) {
                        return 0;
                    }
                }
                return -1;
            }
        }));
    }

    private void generateEmptyRectangles(double minimumArea) {

        int[] relativeCoords = new int[pts.size()];
        /* G�r en kopia av punktlistan som �r sorterad i y-v�rden (DEcending)*/
        ArrayList<Point> ptsYSorted = (ArrayList<Point>) this.pts.clone();

        Collections.sort(ptsYSorted, (new Comparator<Point>() {

            public int compare(Point a, Point b) {
                if (a.y < b.y) {
                    return 1;
                }

                return -1;
            }
        }));

        for (int i = 0; i < relativeCoords.length; i++) {
            relativeCoords[i] = ptsYSorted.indexOf(pts.get(i));
        }

        int pointCount = pts.size();
        for (int yStart = -1; yStart < pointCount; yStart++) {
            for (int xStart = -1; xStart < pointCount; xStart++) {
                int nextStop = pointCount;
                int newNextStop = nextStop;

                for (int yEnd = yStart + 1; yEnd <= pointCount; yEnd++) {
                    for (int xEnd = xStart + 1; xEnd <= nextStop; xEnd++) {
                        //System.out.println(yStart+","+xStart+"-"+yEnd+","+xEnd);
                        int xs, ys, w, h;
                        if (xStart == -1) {
                            xs = 0;
                        } else {
                            xs = (int) pts.get(xStart).getX();
                        }

                        if (yStart == -1) {
                            ys = y;
                        } else {
                            ys = (int) ptsYSorted.get(yStart).getY();
                        }

                        if (xEnd == pointCount) {
                            w = x - xs;
                        } else {
                            w = (int) pts.get(xEnd).getX() - xs;
                        }

                        if (yEnd == pointCount) {
                            h = ys;
                        } else {
                            h = ys - (int) ptsYSorted.get(yEnd).getY();
                        }



                        if (w * h >= minimumArea) {
                            emptyRectangles.add(new Rectangle(xs, ys - h, w, h));
                        }

                        if (xEnd < pointCount && yEnd == relativeCoords[xEnd]) {
                            newNextStop = xEnd;
                            //System.out.println("Fann p");
                        }

                    }
                    nextStop = newNextStop;
                }

            }
        }
        /* sort them by area in descending order */
        Collections.sort(emptyRectangles, new Comparator<Rectangle>() {

            public int compare(Rectangle a, Rectangle b) {
                if (a.width * a.height > b.width * b.height) {
                    return -1;
                } else if (a.width * a.height < b.width * b.height) {
                    return 1;
                } else {
                    return 0;
                }

            }
        });
    }

    private void generateAllMaximalRectangles() {

        /* find and merge all the rectangles into our list */
        ArrayList<Rectangle> rectanglesFromAxis = generateRectanglesFromAxis();
        ArrayList<Rectangle> rectanglesFromPoint = generateRectanglesFromPoints();
        this.allMaximalRectangles.addAll(rectanglesFromPoint);
        this.allMaximalRectangles.addAll(rectanglesFromAxis);

        /* sort them by area in descending order */
        removeDuplicate(this.allMaximalRectangles);
        Collections.sort(this.allMaximalRectangles, new Comparator<Rectangle>() {

            public int compare(Rectangle a, Rectangle b) {
                if (a.width * a.height > b.width * b.height) {
                    return -1;
                } else if (a.width * a.height < b.width * b.height) {
                    return 1;
                } else {
                    return 0;
                }

            }
        });
    }

    /**
     *
     * @return 
     */
    private ArrayList<Rectangle> generateRectanglesFromPoints() {

        /* need a copy since we pass pointers in java arguments */
        ArrayList<Point> ptscpy = new ArrayList<Point>(this.pts);
        ArrayList<Rectangle> allRecs = new ArrayList<Rectangle>();

        /* for each point in our sorted list, we generate all maximal empty rectangles 
         * that has this point as a left border. We only need to consider points that are 
         * greater than this one for the other sides of the rectangles. */

        for (Point p : this.pts) {
            ptscpy.remove(p);
            if (!(p.x == 0 || p.x == x || p.y == 0 || p.y == y)) {
                allRecs.addAll(genRecs(p, ptscpy));
            }
        }

        return allRecs;
    }

    /**
     *
     * @return
     */
    private ArrayList<Rectangle> generateRectanglesFromAxis() {

        ArrayList<Rectangle> allRecs = new ArrayList<Rectangle>();

        /* we start at y = 0 and step through all points, discarding the ones lies
         * on the left border of a maximal empty rectangle (MER) with width
         * x (maximum x-value). We can do this because there can be no other MER:s 
         * inside a MER*/

        /* We can not just do this for the MER with lowest height, test point (0, 0) with 
         *  [(5,6), (10,1), (20, 4)] (the method allRecs will not return rectangles with 
         *  height 1).
         * 
         * */

        int y_ = 0;
        Point p = new Point(0, y_);
        ArrayList<Rectangle> recsFromPnt = null;
        while (y_ < this.y) {

            p.y = y_;
            recsFromPnt = genRecs(p, this.pts);
            int maxHeight = 0;
            for (Rectangle r : recsFromPnt) {
                if (r.width == this.x) {
                    maxHeight = r.height;
                }
            }
            if (maxHeight > 0) {
                y_ += (maxHeight + 1);
            } else {
                y_++;
            }
            allRecs.addAll(recsFromPnt);
        }

        return allRecs;
    }

    /**
     *
     * @param left
     * @param index
     * @param currentSolution
     * @param totalArea
     */
    public void branchAndBound(int left, int index, int[] currentSolution, int totalArea) {
        this.calls++;
        if (left == 0) {
            if (totalArea >= this.getMax()) {
                this.max = totalArea;
                this.solutionArray = currentSolution;
            }
            return;
        }
        for (int i = index; i < rectangleList.size(); i++) {
            if (i > indexSmallestRec) {
                // How deep are we searching?
                indexSmallestRec = i;
            }
            if (!intersectsAny(i, currentSolution)) {
                if ((totalArea + upperBound(i, left)) <= this.getMax()) {
                    return;
                }
                int[] oneAdded = Arrays.copyOf(currentSolution, currentSolution.length + 1);
                oneAdded[currentSolution.length] = i;
                Rectangle addedRec = rectangleList.get(i);
                branchAndBound(left - 1, i + 1, oneAdded, totalArea + (addedRec.height * addedRec.width));
            }
        }
    }

    /**
     * Generate the MER with point p as the left side.
     * @param p A point less than the points in pts.
     * @param pts A sorted set of points greater than p.
     * @return A list of MER with point p as left side.
     */
    private ArrayList<Rectangle> genRecs(Point p, ArrayList<Point> pts) {
        /* Point p block the rectangles on the left side. The method works like 
         * it got two staircases one above and below. That meets then a point in pts
         * got the same y-value as p.*/

        Point dummyPnt = new Point(this.x, p.y); // So we hit the vertical line (max_x, y)

        pts.add(pts.size(), dummyPnt);
        ArrayList<Rectangle> emptyRecs = new ArrayList<Rectangle>();
        int minX = p.x, maxX = this.x, minY = 0, maxY = this.y;
        for (Point p_ : pts) {
            /* Continue if point is just below...*/
            if (p_.x == p.x) {
                continue;
                /* The point must lie inside minY and MaxY. */
            } else if (minY < p_.y && p_.y < maxY) {
                /* If the point is not on the same vertical line as maxX, add a rectangle*/
                /* Test (1,5) with [(3,3),(3,4)], otherwise duplicates. */
                if (!(maxX == p_.x) || (p_.x == this.x)) {
                    maxX = p_.x;
                    /* Not to narrow/thin. */
                    if (!(maxX - minX < 2 || maxY - minY < 2)) {
                        emptyRecs.add(new Rectangle(minX, minY, maxX - minX, maxY - minY));
                    }
                    /* A point with the same y-value blocks any further extension in x-direction.*/
                    if (p_.y == p.y) {
                        break;
                    }
                }
                /* Add a new "step" to one of the staircases. */
                if (p_.y > p.y) {
                    maxY = p_.y;
                } else {
                    minY = p_.y;
                }
            }
        }
        pts.remove(dummyPnt);
        return emptyRecs;
    }

    /**
     *
     * @param arlList
     */
    private static void removeDuplicate(ArrayList<?> arlList) {
        HashSet h = new HashSet(arlList);
        arlList.clear();
        arlList.addAll(h);
    }

    protected boolean intersectsAny(int candidate, int[] chosen) {
        for (int i : chosen) {
            if (rectangleList.get(i).intersects(rectangleList.get(candidate))) {
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @param index
     * @param nrLeft
     * @return
     */
    protected int upperBound(int index, int nrLeft) {
        return nrLeft * this.rectangleList.get(index).height * this.rectangleList.get(index).width;
    }

    /**
     *
     * @param solution
     */
    private void setSolutionList(int[] solution) {
        this.solutionList.clear();
        for (int i : solution) {
            this.solutionList.add(this.getRectangleList().get(i));
        }
    }

    /**
     * @return the calls
     */
    public int getCalls() {
        return calls;
    }

    /**
     * @return the max
     */
    public int getMax() {
        return max;
    }

    /**
     * @return the bestSolAsInts
     */
    public int[] getBestSolAsInts() {
        return solutionArray;
    }

    /**
     * @return the solutionList
     */
    public ArrayList<Rectangle> getBestSolAsList() {
        this.setSolutionList(this.solutionArray);
        return this.solutionList;
    }

    /**
     * @return the pts
     */
    public ArrayList<Point> getPts() {
        return pts;
    }

    /**
     * @return the indexSmallestRec
     */
    public int getIndexSmallestRec() {
        return indexSmallestRec;
    }

    /**
     * @return the allMaximalRectangles
     */
    public ArrayList<Rectangle> getAllMaximalRectangles() {
        return allMaximalRectangles;
    }

    public ArrayList<Rectangle> getAllEmptyRectangles() {
        return emptyRectangles;
    }

    /**
     * @return the seed
     */
    public int getSeed() {
        return seed;
    }

    /**
     * @return the rectangleList
     */
    public ArrayList<Rectangle> getRectangleList() {
        return rectangleList;
    }

    private static boolean containsPoint(ArrayList<Point> pts, ArrayList<Rectangle> recs) {
        for (Point p : pts) {
            for (Rectangle r : recs) {
                if (r.contains(p) && (p.x != r.x || p.y != r.y ||
                        p.x != r.x + r.width || p.y != r.y + r.height)) {
                    return true;
                }
            }
        }
        return false;
    }
}


 